package divide;
public class Solution {
    public int divide(int dividend, int divisor) {

        if(dividend==Integer.MIN_VALUE){
            if(divisor==1){
                return Integer.MIN_VALUE;
            }
            if(divisor==-1){
                return Integer.MAX_VALUE;
            }
        }
        if(dividend==Integer.MAX_VALUE){
            if(divisor==1){
                return Integer.MAX_VALUE;
            }if (divisor==-1){
                return Integer.MIN_VALUE;
            }
        }

        long t=(long) Math.abs(dividend);
        long d=(long) Math.abs(divisor);
        int neg=(t^d)<0?-1:1;
        return (int)fun(t,d)*neg;
    }
    long fun(long dividend,long divisor){
        if(dividend<divisor){
            return 0;
        }else if(dividend==divisor){
            return 1;
        }
        int i=0;
        while(true){
            if(dividend>>i+1>=divisor){
                i=i+1;
            }else{
                break;
            }
        }//最多有多少个2^n个divisor相加<=dividend
        return (1<<i)+fun(dividend-(divisor<<i),divisor);
    }
}

//10/4 =2
//10>>1=5
//10>>2=2
//10-2<<2=2
// 2>>2=1;

//90/3 = 30
// 90>>1=45
// 90>>2=22
// 90>>3=11
// 90>>4=5
// 90>>5=2 <3



// 100/3
// 100>>1 = 50
// 100>>2 = 25
// 100>>3 = 12
// 100>>4 = 6
// 100>>5 =3
// 3<<5=3*32=96
// 100-96=4
// 4>>1=2 <3
// 60/3 = 20
// 60>>1=30
// 60>>2= 15
//60>>3=7
//60>>4=3
// 3*2^4=3*16=48              j=4;
// 60-48=12
// 12>>1=6
// 12>>2=3
// 12>>3=1